package binomialcoefficients;

import java.math.BigInteger;
import java.util.Scanner;

public class Solution {
	private static BigInteger divisibleCoefficients(BigInteger n, BigInteger P) {
		BigInteger m = n, nondiv = BigInteger.ONE;
		while(m.compareTo(BigInteger.ZERO) > 0) {
			nondiv = nondiv.multiply(m.remainder(P).add(BigInteger.ONE));
			m = m.divide(P);
		}
		return n.add(BigInteger.ONE).subtract(nondiv);
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		try {
			int T = in.nextInt();
			for(int t = 0; t < T; t++) {
				BigInteger n = in.nextBigInteger();
				BigInteger P = in.nextBigInteger();
				System.out.println(divisibleCoefficients(n, P));
			}
		} finally {
			in.close();
		}
	}
}
